package com.zjj.algorithm.learning.leetcode.matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵 中档题
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * <p>
 * 输入：matrix =
 * [
 * [1,2,3],
 * [4,5,6],
 * [7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 *
 * @author zjj_admin
 * @date 2022/11/25 17:12
 */
public class SpiralMatrix {

    public static void main(String[] args) {

        int[][] arr1 = new int[][]{
                {1, 2, 3},
                {4, 5, 2},
                {7, 8, 9}
        };
        int[][] arr2 = new int[][]{
                {1, 2, 3, 4, 2},
                {5, 6, 7, 8, 4},
                {9, 10, 11, 12, 6},
                {13, 14, 15, 16, 8}
        };
        int[][] arr3 = {
                {1}
        };
        List<Integer> res = spiralOrder2(arr3);
        System.out.println("res = " + res);
    }

    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.9 MB
     * 击败
     * 9.74%
     *
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder2(int[][] matrix) {
        int height = matrix.length;
        int with = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int up = 0, down = height - 1, left = 0, right = with - 1;
        int i, j = 0;
        while (true) {
            //上边界
            for (j = left; j <= right; j++) {
                res.add(matrix[up][j]);
            }
            //上边界向下移
            if (++up > down) {
                break;
            }

            //右边界
            for (i = up; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            //右边界向左移
            if (--right < left) {
                break;
            }

            //下边界
            for (j = right; j >= left; j--) {
                res.add(matrix[down][j]);
            }
            //下边界向上移
            if (--down < up) {
                break;
            }

            //左边界
            for (i = down; i >= up; i--) {
                res.add(matrix[i][left]);
            }
            //左边界向右移
            if (++left > right) {
                break;
            }
        }

        return res;
    }

    /**
     * 顺时针遍历，此方法只能用于正方形 边长 >= 3 的方阵
     *
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int i = 0;
        int j = 0;
        int value;
        //走的方向 1，表示向右，2表示向下，3表示向左，4表示向上
        int model = 1;
        while (true) {
            value = matrix[i][j];
            if (value > Integer.MIN_VALUE) {
                res.add(value);
                matrix[i][j] = Integer.MIN_VALUE;
            }

            if (model == 1) {
                if (j + 1 < matrix[i].length && matrix[i][j + 1] > Integer.MIN_VALUE) {
                    j++;
                    continue;
                } else {
                    model = 2;
                }
            } else if (model == 2) {
                if (i + 1 < matrix.length && matrix[i + 1][j] > Integer.MIN_VALUE) {
                    i++;
                    continue;
                } else {
                    j--;
                    model = 3;
                }
            } else if (model == 3) {
                if (j - 1 >= 0 && matrix[i][j - 1] > Integer.MIN_VALUE) {
                    j--;
                    continue;
                } else {
                    model = 4;
                }
            } else {
                if (i - 1 >= 0 && matrix[i - 1][j] > Integer.MIN_VALUE) {
                    i--;
                    continue;
                } else {
                    model = 1;
                }
            }
            //当遍历结束时需要跳出村换
            if ((i + 1 < matrix.length && matrix[i + 1][j] == Integer.MIN_VALUE)
                    && (i - 1 >= 0 && matrix[i - 1][j] == Integer.MIN_VALUE)
                    && (j + 1 < matrix[i].length && matrix[i][j + 1] == Integer.MIN_VALUE)
                    && (j - 1 >= 0 && matrix[i][j - 1] == Integer.MIN_VALUE)) {
                break;
            }
        }
        return res;
    }
}
